//  Spea2Fitness.java
//
//  Author:
//       Antonio J. Nebro <antonio@lcc.uma.es>
//       Juan J. Durillo <durillo@lcc.uma.es>
//
//  Copyright (c) 2011 Antonio J. Nebro, Juan J. Durillo
//
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU Lesser General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU Lesser General Public License for more details.
// 
//  You should have received a copy of the GNU Lesser General Public License
//  along with this program.  If not, see <http://www.gnu.org/licenses/>.
package jmetal.util;

import jmetal.core.SolutionSet;
import jmetal.util.comparators.DominanceComparator;
import jmetal.util.comparators.FitnessComparator;

import java.util.*;

/**
 * This class implements some facilities for calculating the Spea2 fitness
 */
public class Spea2Fitness {

    /**
     * Stores the distance between solutions
     */
    private double[][] distance = null;

    /**
     * Stores the solutionSet to assign the fitness
     */
    private SolutionSet solutionSet_ = null;

    /**
     * stores a <code>Distance</code> object
     */
    private static final Distance distance_ = new Distance();

    /**
     * stores a <code>Comparator</code> for distance between nodes checking
     */
    private static final Comparator distanceNodeComparator = new DistanceNodeComparator();

    /**
     * stores a <code>Comparator</code> for dominance checking
     */
    private static final Comparator dominance_ = new DominanceComparator();

    /**
     * Constructor. Creates a new instance of Spea2Fitness for a given
     * <code>SolutionSet</code>.
     *
     * @param solutionSet The <code>SolutionSet</code>
     */
    public Spea2Fitness(SolutionSet solutionSet) {
        distance = distance_.distanceMatrix(solutionSet);
        solutionSet_ = solutionSet;
        for (int i = 0; i < solutionSet_.size(); i++) {
            solutionSet_.get(i).setLocation(i);
        } // for
    } // Spea2Fitness

    /**
     * Assigns fitness for all the solutions.
     */
    public void fitnessAssign() {
        double[] strength = new double[solutionSet_.size()];
        double[] rawFitness = new double[solutionSet_.size()];
        double kDistance;

        /*Compara cada individuo com todos os outros da populacao adicionando 1.0 
         a cada solucao que i domina*/
    //Calculate the strength value
        // strength(i) = |{j | j <- SolutionSet and i dominate j}|
        for (int i = 0; i < solutionSet_.size(); i++) {
            for (int j = 0; j < solutionSet_.size(); j++) {
                if (dominance_.compare(solutionSet_.get(i), solutionSet_.get(j)) == -1) {
                    strength[i] += 1.0;
                } // if        
            } // for
        } // for

        /*Compara cada individuo com todos os outros da populacao adicionando ao 
         rawFitness de i todo o valor de strength do individuo que ele domina. 
         Selecionando dessa forma os individuos mais fortes*/
    //Calculate the raw fitness
        // rawFitness(i) = |{sum strenght(j) | j <- SolutionSet and j dominate i}|
        for (int i = 0; i < solutionSet_.size(); i++) {
            for (int j = 0; j < solutionSet_.size(); j++) {
                if (dominance_.compare(solutionSet_.get(i), solutionSet_.get(j)) == 1) {
                    rawFitness[i] += strength[j];
                } // if
            } // for
        } // for

        /*Calcula a distancia de cada individuo em relacao a toda populacao de 
         acordo com a distancia da matriz de distancias e o valor de rawFitness 
         conquistado*/
    // Add the distance to the k-th individual. In the reference paper of SPEA2, 
        // k = sqrt(population.size()), but a value of k = 1 recommended. See
        // http://www.tik.ee.ethz.ch/pisa/selectors/spea2/spea2_documentation.txt
        int k = 1;
        for (int i = 0; i < distance.length; i++) {
            Arrays.sort(distance[i]);
            kDistance = 1.0 / (distance[i][k] + 2.0); // Calcule de D(i) distance
            //population.get(i).setFitness(rawFitness[i]);
            solutionSet_.get(i).setFitness(rawFitness[i] + kDistance);
        } // for                  
    } // fitnessAsign

    /**
     * Gets 'size' elements from a population of more than 'size' elements using
     * for this de enviromentalSelection truncation
     *
     * @param size The number of elements to get.
     */
    public SolutionSet environmentalSelection(int size) {

        if (solutionSet_.size() < size) {
            size = solutionSet_.size();
        }

        // Create a new auxiliar population for no alter the original population
        SolutionSet aux = new SolutionSet(solutionSet_.size());

        int i = 0;
        while (i < solutionSet_.size()) {
            if (solutionSet_.get(i).getFitness() < 1.0) {
                aux.add(solutionSet_.get(i));
                solutionSet_.remove(i);
            } else {
                i++;
            } // if
        } // while

        /*Verifica se a populacao (aux) possui o tamanho determinado como arquivo
        1- Caso não tenha, conpleta-se com outras soluções qualquer... e retorna
        2- Caso possua a quantidade determinada, retorna a lista
        3- Caso seja maior que a definida, aplica-se o truncamento*/
        if (aux.size() < size) {
            Comparator comparator = new FitnessComparator();
            solutionSet_.sort(comparator);
            int remain = size - aux.size();
            for (i = 0; i < remain; i++) {
                aux.add(solutionSet_.get(i));
            }
            return aux;
        } else if (aux.size() == size) {
            return aux;
        }
        /*************************TRUNCAMENTO**************************/
        /*Calcula a distancia euclidiana entre os objetivos de cada solucao
        Ex:              Obj1, Obj2
            Individuo1 = [200, 300]
            Individuo2 = [220, 700]*/
        double[][] distance = distance_.distanceMatrix(aux);
        List< List<DistanceNode>> distanceList = new LinkedList< List<DistanceNode>>();
        for (int pos = 0; pos < aux.size(); pos++) {
            aux.get(pos).setLocation(pos);
            List<DistanceNode> distanceNodeList = new ArrayList<DistanceNode>();
            for (int ref = 0; ref < aux.size(); ref++) {
                if (pos != ref) {
                    distanceNodeList.add(new DistanceNode(distance[pos][ref], ref));
                } // if
            } // for
            distanceList.add(distanceNodeList);
        } // for                        

        /*Ordena todas as listas com as distancias*/
        for (List<DistanceNode> aDistanceList : distanceList) {
            Collections.sort(aDistanceList, distanceNodeComparator);
        } // for

        
        /*Processa enquanto a populacao for maior que a definida como maxima
        A cada iteracao do While, busca pela menor distancia para ser removida
        Vide grafico do artigo SPEA. 
        Menor valor indica que as solucoes estao muito perto, prejudicando a 
        diversidade, por isso sao removidas.*/
        while (aux.size() > size) {
            double minDistance = Double.MAX_VALUE;
            int toRemove = 0;
            i = 0;
            for (List<DistanceNode> dn : distanceList) {
                if (dn.get(0).getDistance() < minDistance) {
                    toRemove = i;
                    minDistance = dn.get(0).getDistance();
                    //i y toRemove have the same distance to the first solution
                } else if (dn.get(0).getDistance() == minDistance) {
                    int k = 0;
                    while ((dn.get(k).getDistance() == distanceList.get(toRemove).get(k).getDistance()) && k < (distanceList.get(i).size() - 1)) {
                        k++;
                    }

                    if (dn.get(k).getDistance() < distanceList.get(toRemove).get(k).getDistance()) {
                        toRemove = i;
                    } // if
                } // if
                i++;
            } // while

            int tmp = aux.get(toRemove).getLocation();
            aux.remove(toRemove);
            distanceList.remove(toRemove);

            for (List<DistanceNode> aDistanceList : distanceList) {
                Iterator<DistanceNode> interIterator = aDistanceList.iterator();
                while (interIterator.hasNext()) {
                    if (interIterator.next().getReference() == tmp) {
                        interIterator.remove();
                    } // if
                } // while
            } // while      
        } // while   
        return aux;
    } // environmentalSelection   
} // Spea2Fitness
